﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/sort-array-by-increasing-frequency/
/*
题目描述：
给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。 
请你返回排序后的数组。

 

示例 1：
输入：nums = [1,1,2,2,2,3]
输出：[3,1,1,2,2,2]
解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。

示例 2：
输入：nums = [2,3,1,3,2]
输出：[1,3,3,2,2]
解释：'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。

示例 3：
输入：nums = [-1,1,-6,4,5,-6,1,4,1]
输出：[5,-1,4,4,-6,-6,1,1,1]
 

提示：
1 <= nums.length <= 100
-100 <= nums[i] <= 100
*/

// 开始解题：
 // 方法1——键值对映射
typedef struct KeyVal {
    int val;
    int fre;
} KeyVal;

int cmp(const void* p1, const void* p2) {
    assert(p1 && p2);
    int val1 = (*(KeyVal*)p1).val;
    int val2 = (*(KeyVal*)p2).val;
    int fre1 = (*(KeyVal*)p1).fre;
    int fre2 = (*(KeyVal*)p2).fre;

    if (fre1 != fre2) {
        return (*(KeyVal*)p1).fre - (*(KeyVal*)p2).fre;
    }
    return val2 - val1;
}
int* frequencySort(int* nums, int numsSize, int* returnSize) {
    assert(nums && returnSize);
    *returnSize = numsSize;
    int* temp = (int*)malloc(205 * sizeof(int));
    if (NULL == temp) {
        perror("malloc fail!\n");
        exit(-1);
    }
    memset(temp, 0, 205 * sizeof(int));
    int i = 0;
    for (i = 0; i < numsSize; i++) {
        temp[nums[i] + 100]++;
    }
    int count = 0;
    for (i = 0; i < 205; i++) {
        if (temp[i] != 0) {
            count++;
        }
    }
    KeyVal* keyval = (KeyVal*)malloc(count * sizeof(KeyVal));
    if (NULL == keyval) {
        perror("malloc fail!\n");
        exit(-1);
    }
    int n = 0;
    for (i = 0; i < 205; i++) {
        if (temp[i] != 0) {
            keyval[n].val = i - 100;
            keyval[n].fre = temp[i];
            n++;
        }
    }
    // 排序
    qsort(keyval, count, sizeof(KeyVal), cmp);
    int* answer = (int*)malloc(numsSize * sizeof(int));
    if (NULL == answer) {
        perror("malloc fai!\n");
        exit(-1);
    }
    n = 0;
    int j = 0;

    for (i = 0; i < count; i++) {
        for (j = 0; j < keyval[i].fre; j++) {
            answer[n] = keyval[i].val;
            n++;
        }
    }
    return answer;
}

